1. Field of the Invention
The present invention relates to methods and systems of prediction. The main object of the present invention is an extension of cognitive predicting methods on non-stationary processes.
2. The Prior Art
Every process can be viewed as a product of some entity""s functioning. From that position, we may look at the process as the entity""s output. We also may use the term object of prediction meaning the entity whose output shall be predicted. The binary process is frequently used for a representation of any other process that permits such mapping. All further descriptions will be done in view of the binary process prediction.
The majority of known methods, algorithms, and systems, which are capable of prediction of the entity""s output, use a priori knowledge of that entity""s properties. Typically, the entity""s properties are described in the form of various types of mathematical models such as sets of algebraic, differential, integral, stochastic equations, and their combinations. The predicting systems that employ the entity""s model span the wide range between the first attempts for extrapolation by Newton, Lagrange, etc. [G. A. Korn, 1961], and modern adaptive predictors [U.S. Pat. No. 5,424,942, 07/1995, 364#164, Dong,]. The degree of complexity of prediction rises continuously. The development of cognitive predicting algorithms was inspired by a problem of an accurate prediction for an entity that is not able to provide complete information about its varying parameters and structure. These algorithms use cloning of evolutionary principals of biological systems. They belong to a set of genetic algorithms whose theory Dr. J. Holland developed in 1975. There are important features that describe uniqueness of the predicting systems utilizing a genetic algorithm approach [J. Holland, 1975, J. R. Koza, 1992, U.S. Pat. No. 5,136,686, 08/1992, Koza, K. De Jong and W. Spears, 1993]:
Object of prediction is stationary or quasi-stationary
The process to be predicted, employs a binary string as its internal representation
A Genetic Algorithm Representative Schema is a set of predicting solutions that are functions of the process"" argument. Every generation of such schema is a product of a multi-step optimization procedure that includes the Natural Selection Algorithm for an appropriate selection of the predicting solutions; Evolutionary Operators such as crossover, mutation, permutation, proportional reproduction, inversion, etc., for the new solutions generation; and a Fitness Function to be a measure of performance for each of those solutions
The representative schema optimization procedure acts on the specified interval of the binary process history to train the predicting system in recognizing of specifics of the process that is subjected to prediction
The predicting system produces a prediction of the forthcoming process element via calculating an output of the optimal predicting function at the next value of its argument.
A powerful extended genetic algorithm developed by J. Koza [U.S. Pat. No. 5,136,686, 08/1992] is a good material for a discussion of strengths and weaknesses of the genetic algorithm approach in the context of non-stationary process prediction. The J. Koza""s genetic algorithm is nonlinear. It not only includes the natural selection method and evolutionary operators, but also breaks down a problem into a hierarchy of subordinating sub-problems. This algorithm is free of the uniformity constraint that requires keeping the same size for all members of the population of predicting solutions. The J. Koza""s genetic algorithm was not specifically designed for prediction. In the most general form given in the patent disclosure, this algorithm has the following description. xe2x80x9cThe process of the present invention operates upon a population of entities which accomplish tasks and can vary in size and shape. Each iteration of the process comprises activating, selecting, choosing, performing, and adding. First, each entity activates to accomplish its goal and produces a result. Second, a value is associated with the result of each activation and assigned to the corresponding entity. Third, at least one entity having a relatively high associated value is selected. Next, an operation is chosen from crossover, fitness proportionate reproduction, mutation, or permutation. If crossover is chosen, then the selected entity performs the crossover operation. Crossover creates new entities by combining portions of at least one selected entity with portions of at least one another entity. Fitness proportionate reproduction retains the selected entity in the population. Mutation randomly alters a small random part of an entity. Permutation reorders the parts of an entity without a net gain or loss. Finally, the newly produced entities are added to the population.
xe2x80x9cMany seemingly different problems can be reformulated into a problem requiring discovery of mathematical expression or computer program that produces some desired output for particular inputs. When viewed in this way, the process of solving these seemingly different problems becomes equivalent to searching a space of possible mathematical expressions or computer programs for a most fit individual mathematical expression or computer program.xe2x80x9d Naturally, Dr. Koza suggested to use this algorithm for prediction of xe2x80x9c. . . the future elements of a sequence of numbers from a sampling of early numbers from the sequence [U.S. Pat. No. 5,136,686, 08/1992, p. 221].xe2x80x9d
A possible binary process element predicting system that corresponds to the described above genetic algorithm may be presented with a block diagram depicted on the FIG. 1. The following conventions are present in the above illustration.
There are two types of predicting procedures in the system. The first procedure is an actual predicting procedure. The second procedure is a retrospective predicting procedure. An operator F that has the following definition provides both procedures.
∀xcfx84=(t1,t2, . . . , tp),xcfx84=tiF[x(xcfx84)]xe2x89xa1f(tixe2x88x921) xe2x80x83xe2x80x83(1.1) 
f(ti+1)=x(ti+1)xe2x80x9ccorrect predictionxe2x80x9d
ti=tpf(ti+1)xe2x88x92actual prediction 
ti less than tpf(tixe2x88x921)xe2x88x92retrospective prediction 
Here tp is a value of the latest existing discrete argument xcfx84=(t1, t2, . . . , tp) of the binary process x(xcfx84). When the retrospective predicting procedure is active, it is assumed that the forthcoming element of the binary process is unknown. This procedure is used at the stage of genetic algorithm representative schema optimization. When the actual predicting procedure is active, it means that the forthcoming element of the binary process is really unknown. The discrete argument xcfx84 of the binary process x(xcfx84) is not necessarily a time variable.
The binary process predicting system that is based on the described above genetic algorithm operates as follows. Each element of the binary process x(xcfx84) goes to the storage (H) where it becomes a binary string h[x(xcfx84),ti] element; ti is an observer""s position point, i=1,2, . . . , p. The system selects an interval [tq,tr], tq less than tr≲tp on that binary string. Then, the Predicting Functions Generator (PFG) inserts an initial population of the binary process"" predicting functions pfk(xcfx84,tq,tr)xcex5PF1, k=1,2, . . . , K. Each predicting function is made up of binary tokens, and may be considered as a chromosome. Then, the predicting system initiates training until it finds the optimal predicting function pfopt(xcfx84,tq,tr), xcfx84xcex5[tq,tr]. The following recursive expressions give a formal description of a search for the optimal predicting function.
PFjxe2x88x921=PFG[PFj,xcfx86j(xcfx84)],j=1,2, . . . ,J xe2x80x83xe2x80x83(1.2) 
(An iteration index j is omitted further in order to simplify notations) 
∀xcfx84=(t1,t2, . . . , tp),xcfx84=tiF[x(xcfx84)]xe2x89xa1f(ti+1) 
xcfx86(xcfx84,tq,tr)="PHgr"[R(xcfx84),W(xcfx84)]=xcexa3[R(xcfx84)]xcexa3xe2x88x921[W(xcfx84)],xcfx86(xcfx84,tq,tr)≳0 
R(xcfx84)={R1(xcfx84),R2(xcfx84), . . . , RN(xcfx84)},W(xcfx84)={W1(xcfx84),W2(xcfx84), . . . ,WN(xcfx84)}
∃pfopt(xcfx84,tq,tr)xcex5PF,xcfx86(xcfx84)xe2x86x92max(perfect fit) 
∃pfm(xcfx84,tq,tr)xcex5PF,xcfx86(xcfx84)xe2x88x92xcfx86o greater than 0, xcfx86o greater than 0, m=1,2, . . . , M(good fit) 
f(ti+1)=x(ti+1)Ri(xcfx84)=1xe2x88x92correct prediction 
f(ti+1)xe2x89xa0x(tixe2x88x921)Ri(xcfx84)=0xe2x88x92incorrect prediction, i=1,2, . . . ,N 
Wi(xcfx84)= Ri(xcfx84) 
The fitness operator "PHgr" of the (1.2) may have a different view. However, every fitness function shares a common feature. Each fitness function in the predicting system provides an integral evaluation of the system""s predicting ability. This evaluation is calculated on the interval [tq,tr] where (trxe2x88x92tq) greater than  greater than 1. The form of the fitness operator presented in the expressions (1.2) reflects the fact that the efficiency of prediction is as higher as there are more correct predictions produced with respect to the amount of incorrect predictions if both of them are observed on the same interval [tq, tr]. The number Nxe2x89xa1Nj of components of the vectors Rj and Wj is equal to the cardinal number of the PFj-set for each iteration j=1,2, . . . , J. The PFS - operator of the (1.2) is responsible for changes in the population of pf - functions. This operator involves evolutionary operations to modify pf - functions from the previous iteration. It also produces a selection of those pf - functions which satisfy to the xe2x80x9cgood fitxe2x80x9d selection condition. The xe2x80x9cgood fitxe2x80x9d pf - functions are the source of new members in the PFj+1. Thus, we can see that the fitness function xcfx86 (xcfx84) serves in this predicting algorithm as a measure of how successfully any pf - function returns predictions exclusively on the interval [tq, tr].
The described above method possesses a distinctive peculiarity of the genetic algorithms if viewed from the position of prediction. That is a utilization of the iterative optimization procedure for achieving the optimal predicting function. In this connection, the optimization procedure is defined on the certain interval of the binary process""s xe2x80x9cpastxe2x80x9d such that the search for the optimal predicting solution and the actual prediction are separated from each other.
K. De Jong and W. Spears (1993) concluded in their review on genetic algorithms, that the operational domain of the algorithm developed by J. Koza (1992) and the similar algorithms and systems [U.S. Pat. Nos. 4,697,242, 09/1987, Holland; 5,222,192, 07/1993, Shaefer; 5,255,345, 10/1993, Shaefer] are limited by a stationary state constraint. This constraint requires for every system that involves the genetic algorithm for prediction, to be stationary, or in some particular cases, to be quasi-stationary. It is possible to support Dr. De Jong""s opinion with the help of the following reasoning. Let us assume that the optimal predicting function has been found as a result of training on the interval [tq, tr]. The next step is the actual prediction, when xcfx84 goes farther than the [tq, tr]. However, as long as the arbitrary fitness function is able to evaluate performance of the pf - functions only if (trxe2x88x92t1) greater than  greater than 1, then a possible error in the actual prediction at xcfx84=tr+1, can not affect the PF - set""s membership. It is necessary to carry out several predictions using the pfopt (xcfx84, tq, tr) before the new optimal predicting function pfopt (xcfx84, ts, tr+w) , w greater than  greater than 1 can be determined and the system can use it for prediction. Therefore, that kind of predicting system may work efficiently only if such interval [tr, tr+w], w greater than  greater than 1 exists where the binary process does not change one""s properties. In other words, the object of prediction must be stationary or quasi-stationary in order for the genetic algorithm based predicting system works efficiently. The described above is a projection of the genetic algorithm""s natural limitation on the problem of the binary process prediction.
This is a known fact that differential, integral, stochastic, or any other mathematical models can not entirely represent a non-stationary process. Hence, any methods based on traditional mathematical models are not feasible for non-stationary process prediction. Some of typical non-stationary processes are listed below for a purpose of illustration.
1. Signal-to-noise ratio in a discrete measuring system if at every particular moment of measuring a value of this ratio needs to be predicted
2. Sequential prediction of elements of an econometric time series
3. Game whose random outcome must be predicted at every step and the number of steps are limited
4. Prediction of an object""s failure according to a pre-assigned check-up schedule.
The above listed and the like processes do not have the interval [tr,tr+w], w greater than  greater than 1 where their steadiness or stationarity can be confirmed. Hence, it appears that a predicting system utilizing any genetic algorithm is unable to manage alteration of the non-stationary process"" behavior. Moreover, there are a few fundamental features of the genetic algorithms that definitely resist the solving of the problem of non-stationary process prediction. Those features are:
Generating of new predicting functions through the application of the evolutionary operators such as crossover, mutation, proportional reproduction, etc., to the existing members of the population of predicting functions
Separation of the optimal predicting function Pfopt (xcfx84, tq, tr) determination process from the process of actual prediction such that the optimal predicting function can be defined only on the antecedent interval [tq, tr], (trxe2x88x92tq) greater than  greater than 1, tr≲tp.
In addition, the cognitive predicting system utilizing multi-step optimization for the system""s training requires powerful computing sources. This is also a substantial limitation of the genetic algorithm paradigm.
At the same time, the genetic algorithms carry several significant properties that are vital for the solution of the non-stationary process prediction problem.
First, it is an idea of adaptation [J. H. Holland, 1975]. The adaptation is considered an ability of a system modifying its parameters and structure in response to changes of the system""s environment. In view of the process"" prediction, the role of the environment belongs to the object of prediction.
The second property is an assumption about the existence of a representative set of solutions. A desired solution or solutions may be obtained by applying the Natural Selection Algorithm to the representative set of solutions.
The third property is an idea about the existence of atomic elements (genes) whose combinations construct members (chromosomes) of the representative set of solutions (population of chromosomes).
The last of these properties is a conjecture that chromosomes of different size may exist in the same population of solutions [J. Koza, 1992].
The following questions must be answered when developing the method for a sequential prediction of a binary element""s state in the binary process.
The structure and the algorithm of the predicting system that is enable to adapt to a fast altering behavior of the non-stationary object of prediction.
The predicting procedure that employs the Natural Selection Algorithm.
The generator of predicting functions and the algorithm for these functions update.
The composition, the size, and the property of the set of predicting functions
There are no answers found in scientific literature for these questions. The problem of sequential prediction of a binary element""s state in a binary process finds its solution in the present invention. One object of the present invention is to provide a mathematical method and a computer algorithm to perform real time predictions of binary processes including non-stationary processes. A further object of the present invention is to provide the structure of the cognitive system for a sequential prediction of a binary element""s state in a binary process that increases efficacy of functioning of any entity that includes this system as a subsystem.
The present invention relates to methods and systems of prediction. The present invention provides the method for a sequential prediction of a binary element""s state in a binary process and the system for the method embodiment. The binary processes are frequently used as a representation of a wide range of other processes that can be observed at outputs of various types of objects of prediction. The present invention is based on a representation of the chaotic nature as a xe2x80x9cneighboringxe2x80x9d order regularity whose separate parts preserve some order. The binary process was decomposed and specific atomic binary structures of minimal length were distinguished. A propagation of those structures in both directions of the binary process domain returns a stable, regular image. Such formations were denoted as the Elementary Behavioral Functions. It is observed in the present invention that every binary process x(xcfx84), xcfx84=t1, t2, . . . , tp can be uniquely represented by a sequence of its elementary behavioral functions bk (xcfx84, tk, xcex7k), (k=1, 2, . . . , K),
∀xcfx84xcex5(t1,t2, . . . ,tp),x(xcfx84)=xcexa3bk(xcfx84,tk,xcex7k),xcex7k≳2, tk=tkxe2x88x921+xcex7kxe2x80x83xe2x80x83(2.1) 
dom[bk(xcfx84,tk,xcex7k)]=[tkxe2x88x921,tk]
Here xcex7k is a period of the k-th elementary behavioral function; dom [bk(xcfx84,tk,xcex7k)] is a domain of the function bk(xcfx84,tk,xcex7k) [R. Elmasri and S. Navathe, 1994]. If taken with satisfaction to a condition of orthogonality, these functions become behavioral genes of the binary process, and constitute a genotype BG of the binary process"" behaviors. The behavioral genotype set is defined on a representative interval [tq,tr],
xcex=(trxe2x88x92tq) greater than  greater than 1. Then, the set BG is transformed into a generalized genotype BG* by a union with the set C={c÷(xcfx84), cxe2x88x92(xcfx84)}. Each member of the C-set is a countable sequence of identical states of binary process elements under the condition of c+(xcfx84)= cxe2x88x92(xcfx84) .
It is stated in the present invention that the genotype BG* is quasi-stationary relatively to a character of change of two adherent elementary behavioral functions in the expression (2.1). Every binary process has its inherent behavioral genotype. In the case of a multi-dimensional system each component x(xcfx84) of a vectorial binary process X(xcfx84) has its inherent behavioral genotype.
The process of prediction is recursive. It includes the following basic steps.
1. Determination of the set BG*j of behavioral genes at the moment xcfx84=tr. The set BG*j modifies the previous set BG*jxe2x88x921 which was determined at xcfx84=trxe2x88x92xcexj, xcexjxcex5N, where N denotes the set of natural numbers. If xcfx84xcex5[trxe2x88x92xcexj, tr) then the set BG*jxe2x88x921 is still active.
2. Evaluation of the binary process instability level, or process"" transients effect on process"" predictability, through a calculation of an estimating vector-function xcfx86j={xcfx861j(xcfx84,te,xcexe1),xcfx862j(xcfx84,te,xcexe2), . . . ,xcfx86nj(xcfx84,te,xcexen)} by applying a retrospective predicting procedure; te- evaluation schedule indicator; xcexe-evaluation window
3. Performing an actual dual-stage predicting procedure at xcfx84=tp≳tr. This procedure produces a prediction of a forthcoming binary element""s state x(tp+1) in the binary process X(xcfx84). The procedure is non-iterative and cyclic. Each cycle may contain several predictions. The starting point (tc) for the next cycle is when an error er (tc) of prediction occurs, i.e., ∃tc xcex5xcfx84, f (tc)xe2x89xa1f (tp+1)xe2x89xa0x (tp+1) er(tc)=true, (tc=tc1, tc2, tc3, . . . ). The first stage is for a selection of the set PFk=PFS [BG*j,"ugr" (xcfx86k)], (k=1,2, . . . ) of predicting functions, which are active at the beginning of the k-th cycle of prediction. The PFk- set exists in various alternate versions. The composition of this set is controlled by a function (trademark) (xcfx86k). This function is responsive to the current level of the binary process instability. It is fulfilled in the present invention that a cardinality of the set of predicting functions is inversely related to the evaluated instability level of the binary process; so that, for explicitly non-stationary processes the following statement is competent: PFk⊂ BG*j. The second stage is for prediction directly. The prediction f(xcfx84)xe2x89xa1f(tp+1) is returned by a logical operator F acting upon the set PFk of predicting functions. The output of the prediction f(xcfx84) depends on prediction error""s status of each PFk-set""s member, current efficiency of prediction, and a set of binary indicators modifying a predicting algorithm. The retrospective prediction and the actual prediction both employ the Natural Selection Algorithm in a manner that each member of PFk participates in the current prediction cycle until this member produces an incorrect prediction. Each predicting function may again participate in prediction only in the next predicting cycle.
4. Updating of the behavioral genotype membership and re-estimating of the binary process instability level.
The above-presented method of prediction is used in a predicting system that is the method""s embodiment. The system is comprised of two subsystemsxe2x80x94subsystem SS1, and subsystem SS2. The main objective of the subsystem SS1 is the determination of a composition of the behavioral genotype set. The SS1-subsystem provides such determination on periodical basis. The subsystem SS1 is comprised of the following: a Binary Process Mapping Block (BM), a Binary Process History Storage Block (H), a Behavioral Genotype Creator (BG), a Sampling Block (S), and a Binary Process Shortest History Storage Block (HS). The BM block quantifies, if it is necessary, the signal u(t) from an output of the object of prediction. The quantification may be performed by time and/or by level of the input signal. In total, the output of the BM-block is a vector-function x(xcfx84) of the discrete argument xcfx84=(t1,t2,t3, . . . , tp), where tp is the latest observed value of xcfx84. Every component of x(xcfx84) is processed by a separate identical tract in the SS1, and then the processed data from that tract come to a corresponding tract in the SS2. In order to simplify a disclosure, all descriptions will be further provided for a single component x(xcfx84)xcex5x(xcfx84). A block diagram of the one-dimensional predicting system is shown in FIG. 6. The following conventions are present in the above illustration:
The H-block memorizes each sequential element of the process x(xcfx84) that comes from the BM-block, and forms a binary string [x(xcfx84),tq,tp]xe2x89xa1h [x(xcfx84)]. The string h[x(xcfx84)] goes to an input of the BG-block and to an input of the HS-block. The latter creates a binary string hs[x(xcfx84),ts,tp]xe2x89xa1hs [x(xcfx84)], s≲q. The BG-block makes a decomposition (2.1) of the string h[x(xcfx84)] on the interval [t(rxe2x88x92xcexj), tr], tr≲tp. The ordering number j of the sample""s length xcexj is linked to the value trwhen the decomposition has been initiated. The Sampling Block in the SS1-subsystem""s local feedback controls the value of the xcexj according to a criterion of statistical stability (e.g., the stability of the arithmetic average or both the arithmetic average and the standard deviation) of the biggest elementary behavioral function""s period xcex7max (tr,xcexj) xe2x89xa1xcex7jmax taken from the sample. The xcex7jmax variable defines a cardinal number of the BGj-set. Any methods of statistical analysis are allowed at this stage. A human operator may also set up the value xcexj. The BG - block generates members of the BG*j-set. The j-index in the behavioral genotype notation points to the fact that this set is going to be updated according to some schedule. The BG*-set""s composition data is a main output of the subsystem SS1. Information about the BG*-set membership comes to an input of each Selector of Predicting Functions of the subsystem SS2. The binary string hs[x(xcfx84),ts,tp] goes from an output of the HS-block to another input of the PFS-block of the SS2. The BG-block receives a feedback signal from the SS2. This signal controls the schedule for updating the BG*-set.
The main objective of the subsystem SS2 is selecting the set of predicting functions from the BG*-set and then, performing a prediction. The subsystem SS2 has some distinctive singularities:
The subsystem involves a cyclic, non-iterative, and non-optimizing method of prediction.
The subsystem employs evaluation of the binary process instability. This evaluation is performed for selection of an appropriate set of predicting functions at the initial moment of a predicting cycle.
The subsystem insures that the cardinality of the set of predicting functions is inversely related to the evaluated binary process instability level so that, for the explicitly non-stationary processes PFk⊂ BG*j.
The SS2 subsystem is built from Selectors of Predicting functions (PFSi), Prediction Blocks (Pi), and Binary Process Instability Estimators (Ei), i=1, 2, . . . , m. The subsystem SS2 is comprised of two contours. The first contour is the main contour of the SS2. This contour includes a tract PFSxe2x86x92P that is responsible for the selection of the set PFkxe2x89xa1PF(tck)=PF(BG*j) of predicting functions. These functions are only active in the current predicting cycle. The PFk-set is an output of the PFS-block. The actual prediction f(xcfx84) is the first output of the P-block of the same contour.
The second contour evaluates the binary process instability level. The second contour is comprised of several parallel channels. These channels have an identical structure such as PFSixe2x86x92Pixe2x86x92Ei. Each channel generates a respective component of the estimating vector-function xcfx86(xcfx84, te, xcexe) . The evaluation is performed the application of the retrospective predicting procedure to some interval [tq,tr], tr≲tp of the binary process history. Here, te is an evaluation schedule point, and xcexe=(tq-tr) denotes the length of the evaluation window.
The second output of the P-block of the main contour is an indicator er(xcfx84) of the error of prediction. This indicator signals to the exterior of the SS2-subsystem about the end of the current cycle of actual prediction. The BG-block of the SS1-subsystem takes into account the state of such xe2x80x9cEnd-of-Cyclexe2x80x9d indicator and uses this information for scheduling of the next update of the BG*-set. The er (xcfx84) signal is also used by the SS2 to perform the next instability evaluation of the binary process. A link between the P-block of the SS2-subsystem and the BG-block of the SS2-subsystem closes the global feedback in the predicting system. Depending on the system""s embodiment, a human operator of the predicting system may update the schedules, as well as the setup parameters for the binary process decomposition and subsequent statistical analysis of the elementary behavioral functions.
Predictions performed during a predicting cycle are independent of the evaluation procedure. Each of the three main procedures in the system (the determination of the behavioral genotype, the evaluation of the binary process instability, or process"" transients effect on predictability, and the selection of the set of predicting functions, which are active in the current predicting cycle) can be performed independently and do not affect the system""s speed.
The described above method of prediction increases the efficiency of the binary process prediction. This method extends the applicability of cognitive predicting systems in the field of non-stationary processes. The principal advantage of the method is a more intensive use of the xe2x80x9cpresentxe2x80x9d and the xe2x80x9cnearest pastxe2x80x9d area in the binary process domain. Contrary to prior art""s solutions, the present invention does not demand in the zone [tp, tp+w], (w greater than  greater than 1) of the guaranteed binary process stability. The iterative optimizing xe2x80x9cErrors and Trialsxe2x80x9d genetic algorithm is also absent in the predicting procedure of the present invention. This fact makes possible the application of the present invention to a population of real-time systems.
The present invention can be incorporated in any system that permits mapping of at least one of that system""s output on the space of binary processes.